package com.example.leetcode;

import org.junit.jupiter.api.Test;

import java.util.Stack;

public class LeetCode24 {
    public class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
        }
        // 添加新的结点
        public void add(int newval) {
            ListNode newNode = new ListNode(newval);
            if(this.next == null)
                this.next = newNode;
            else
                this.next.add(newval);
        }
    }

    @Test
    public void Test() {
        ListNode head=new ListNode(1);
        head.add(2);
        head.add(3);
        head.add(4);
        head.add(5);
        reverseList1(head);
        reverseList2(head);
        System.out.println("a");
    }

    public ListNode reverseList1(ListNode head) {
        Stack<ListNode> stack=new Stack<>();
        while (head!=null){
            stack.push(head);
            head=head.next;
        }
        head =stack.pop();
        ListNode cur = head;
        while (stack.size()>0){
            ListNode node =stack.pop();
            node.next=null;
            cur.next=node;
            cur=node;
        }
        return head;
    }
    public ListNode reverseList2(ListNode head) {
        ListNode pre = null, cur = head;
        while(cur != null){
            ListNode nxt = cur.next;
            cur.next = pre;
            pre = cur;
            cur = nxt;
        }
        return pre;
    }

}
